package main

import "fmt"

type point struct {
	x int
	y int
}

func maxDistance(grid [][]int) int {
	dirs := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	queue := []*point{}
	n := len(grid)

	maps := make(map[int]int)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				queue = append(queue, &point{i, j})
				maps[i*n+j] = 0
			}
		}
	}
	res := 0
	for len(queue) > 0 {
		p := queue[0]
		queue = queue[1:]
		dx, dy := p.x, p.y
		step := maps[dx*n+dy]

		for _, v := range dirs {
			nx, ny := dx+v[0], dy+v[1]
			if nx < 0 || nx >= n || ny < 0 || ny >= n {
				continue
			}
			keys := nx*n + ny
			if _, ok := maps[keys]; ok {
				continue
			}
			grid[nx][ny] = step + 1
			queue = append(queue, &point{nx, ny})
			if step+1 > res {
				res = step + 1
			}
			maps[keys] = step + 1
		}
	}

	return res
}

func main() {
	fmt.Println(maxDistance([][]int{{1, 0, 0}, {0, 0, 0}, {0, 0, 0}}))
}
